- Title
- On groups and counter automata
- Creator
- Elder, Murray; Kambites, Mark; Ostheimer, Gretchen
- Relation
- International Journal of Algebra and Computation Vol. 18, Issue 8, p. 1345 - 1364
- Publisher Link
- http://dx.doi.org/10.1142/S0218196708004901
- Publisher
- World Scientific Publishing
- Resource Type
- journal article
- Date
- 2008
- Description
- We study finitely generated groups whose word problems are accepted by counter automata. We show that a group has word problem accepted by a blind n-counter automaton in the sense of Greibach if and only if it is virtually free abelian of rank n; this result, which answers a question of Gilman, is in a very precise sense an abelian analogue of the Muller–Schupp theorem. More generally, if G is a virtually abelian group then every group with word problem recognized by a G-automaton is virtually abelian with growth class bounded above by the growth class of G. We consider also other types of counter automata.
- Subject
- word problem; counter language; G-automaton
- Identifier
- http://hdl.handle.net/1959.13/926900
- Identifier
- uon:9978
- Identifier
- ISSN:0218-1967
- Language
- eng
- Full Text
- Reviewed
- Hits: 2446
- Visitors: 2942
- Downloads: 293
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Author final version | 185 KB | Adobe Acrobat PDF | View Details Download |